﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>
#include <stdio.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/palindrome-linked-list-lcci/
/*
题目描述：
编写一个函数，检查输入的链表是否是回文的。

示例 1：
输入： 1->2
输出： false

示例 2：
输入： 1->2->2->1
输出： true
 
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
*/

 // Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

// 先写一个函数，返回链表的中间节点
struct ListNode* FindMid(struct ListNode* head) {
    if (NULL == head) {
        return NULL;
    }
    struct ListNode* fast = head; // 快指针，一次走两步
    struct ListNode* slow = head; // 慢指针，一次走一步
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

// 再写一个函数，将一个链表翻转
struct ListNode* ReverseList(struct ListNode* head) {
    if (NULL == head) {
        return NULL;
    }
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    struct ListNode* pre = NULL; // cur的前一个节点
    while (cur) {
        pre = cur;
        cur = cur->next;

        // 头插
        pre->next = newhead;
        newhead = pre;
    }
    return newhead;
}
bool isPalindrome(struct ListNode* head) {
    struct ListNode* head1 = head;
    struct ListNode* mid = FindMid(head);
    struct ListNode* head2 = ReverseList(mid);
    struct ListNode* cur1 = head1;
    struct ListNode* cur2 = head2;
    while (cur1 && cur2) {
        if (cur1->val != cur2->val) {
            return false;
        }
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return true;
}
 
